home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / ugraph.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.0 KB  |  172 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  ugraph.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #ifndef LEDA_UGRAPH_H
  18. #define LEDA_UGRAPH_H
  19.  
  20. #include <LEDA/graph.h>
  21.  
  22.  
  23. //-----------------------------------------------------------------------------
  24. // ugraph: base class for all undirected graphs
  25. //-----------------------------------------------------------------------------
  26.  
  27. class ugraph : public graph{
  28.  
  29. public:
  30.  
  31. /*
  32. edge new_edge(node v, node w, edge e1 ,edge e2, int dir1=0,int dir2=0)
  33. { GenPtr x; init_edge_entry(x);
  34.   return new_edge(v,w,e1,e2,x,dir1,dir2);
  35.  }
  36. */
  37.  
  38. edge adj_succ(edge e,node v) const 
  39. { return (v==e->s) ? graph::adj_succ(e) : graph::in_succ(e); }
  40.  
  41. edge adj_pred(edge e,node v) const 
  42. { return (v==e->s) ? graph::adj_pred(e) : graph::in_pred(e); }
  43.  
  44. edge cyclic_adj_succ(edge e,node v)  const
  45. { return (v==e->s) ? graph::cyclic_adj_succ(e) : graph::cyclic_in_succ(e); }
  46.  
  47. edge cyclic_adj_pred(edge e,node v) const
  48. { return (v==e->s) ? graph::cyclic_adj_pred(e) : graph::cyclic_in_pred(e); }
  49.  
  50. void print_edge(edge, ostream& = cout) const;
  51.  
  52. ugraph()  { undirected = true; }
  53.  
  54. ugraph(const graph& a)  : graph(a) { undirected = true; }
  55. ugraph(const ugraph& a) : graph(a) { undirected = true; }
  56.  
  57. ~ugraph() { /* ~graph does the job */ }
  58.  
  59. //subgraph constructors
  60. ugraph(ugraph&, const list<node>&, const list<edge>&);
  61. ugraph(ugraph&, const list<edge>&);
  62.  
  63. ugraph& operator=(const ugraph& a) { graph::operator=(a); 
  64.                                      undirected = true;
  65.                                      return *this; }
  66.  
  67. ugraph& operator=(const graph& a)  { graph::operator=(a); 
  68.                                      undirected= true;
  69.                                      return *this;
  70.                                     }
  71.  
  72. };
  73.  
  74.  
  75.  
  76. //------------------------------------------------------------------------------
  77. // UGRAPH: generic ugraphs
  78. //------------------------------------------------------------------------------
  79.  
  80.  
  81. template<class vtype, class etype>
  82.  
  83. class _CLASSTYPE UGRAPH : public ugraph {
  84.  
  85. vtype X;
  86. etype Y;
  87.  
  88. void copy_node_entry(GenPtr& x) const { x=Copy(ACCESS(vtype,x)); }
  89. void copy_edge_entry(GenPtr& x) const { x=Copy(ACCESS(etype,x)); }
  90.  
  91. void clear_node_entry(GenPtr& x) const { Clear(ACCESS(vtype,x)); }
  92. void clear_edge_entry(GenPtr& x) const { Clear(ACCESS(etype,x)); }
  93.  
  94. void write_node_entry(ostream& o, GenPtr& x) const{ Print(ACCESS(vtype,x),o);}
  95. void write_edge_entry(ostream& o, GenPtr& x) const{ Print(ACCESS(etype,x),o);}
  96.  
  97. void read_node_entry(istream& i, GenPtr& x) { Read(X,i); x=Copy(X); }
  98. void read_edge_entry(istream& i, GenPtr& x) { Read(Y,i); x=Copy(Y); }
  99.  
  100. void init_node_entry(GenPtr& x) { Init(X); x = Copy(X); }
  101. void init_edge_entry(GenPtr& x) { Init(Y); x = Copy(Y); }
  102.  
  103. void print_node_entry(ostream& o, GenPtr& x)  const
  104.      { o << "("; Print(ACCESS(vtype,x),o); o << ")"; }
  105. void print_edge_entry(ostream& o, GenPtr& x)  const
  106.      { o << "("; Print(ACCESS(etype,x),o); o << ")"; }
  107.  
  108. char* node_type()  const { return TYPE_NAME(vtype); }
  109. char* edge_type()  const { return TYPE_NAME(etype); }
  110.  
  111. public:
  112.  
  113. int cmp_node_entry(node x, node y) const { return compare(inf(x),inf(y)); }
  114. int cmp_edge_entry(edge x, edge y) const { return compare(inf(x),inf(y)); }
  115.  
  116. vtype  inf(node v)         const { return ACCESS(vtype,ugraph::inf(v)); }
  117. etype  inf(edge e)         const { return ACCESS(etype,ugraph::inf(e)); }
  118. vtype& operator[] (node v)       { return ACCESS(vtype,entry(v)); }
  119. vtype  operator[] (node v) const { return ACCESS(vtype,ugraph::inf(v)); }
  120. etype& operator[] (edge e)       { return ACCESS(etype,entry(e)); }
  121. etype  operator[] (edge e) const { return ACCESS(etype,ugraph::inf(e)); }
  122. void   assign(node v,vtype x)    { graph::assign(v,Convert(x)); }
  123. void   assign(edge e,etype x)    { graph::assign(e,Convert(x)); }
  124.  
  125.  
  126. node new_node(vtype a) { return graph::new_node(Copy(a)); }
  127.  
  128. edge new_edge(node v, node w, etype a) { return ugraph::new_edge(v,w,Copy(a)); }
  129.  
  130. void clear() { clear_all_entries(); ugraph::clear(); }
  131.  
  132. UGRAPH<vtype,etype>& operator=(const UGRAPH<vtype,etype>& a)
  133. { clear_all_entries();
  134.   ugraph::operator=(*(ugraph*)&a);
  135.   copy_all_entries();
  136.   return *this;}
  137.  
  138. UGRAPH<vtype,etype>& operator=(const graph& a)
  139. { clear_all_entries();
  140.   ugraph::operator=(a);
  141.   copy_all_entries();
  142.   return *this;
  143.  }
  144.  
  145. UGRAPH() {}
  146.  
  147. UGRAPH(const UGRAPH<vtype,etype>& a): ugraph(*(ugraph*)&a) 
  148. { copy_all_entries(); }
  149.  
  150. UGRAPH(const graph& a) : ugraph(a)            
  151. { copy_all_entries(); }
  152.  
  153. ~UGRAPH() 
  154. { if (parent==0) clear_all_entries(); }
  155.  
  156. };
  157.  
  158.  
  159.  
  160. extern void complete_ugraph(ugraph&,int);
  161. extern void random_ugraph(ugraph&,int,int);
  162. extern void test_ugraph(ugraph&);
  163.  
  164. #ifndef __ZTC__
  165. inline void complete_graph(ugraph& U,int n)     { complete_ugraph(U,n); }
  166. inline void random_graph(ugraph& U,int n,int m) { random_ugraph(U,n,m); }
  167. inline void test_graph(ugraph& U)               { test_ugraph(U); }
  168. #endif
  169.  
  170.  
  171. #endif
  172.